// 版权所有2011 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package lzw

import (
	"bufio"
	"errors"
	"fmt"
	"io"
)

// writer是缓冲的、可流动的writer。
type writer interface {
	io.ByteWriter
	Flush() error
}

const (
	// 代码是一个12位的值，编码时存储为uint32以避免
	// 移位位时的类型转换。
	maxCode     = 1<<12 - 1
	invalidCode = 1<<32 - 1
	// 有1个<<12个可能的代码，这是代码数量的上限
	// 任何给定时间点的有效哈希表项。表大小是它的4倍。
	tableSize = 4 * 1 << 12
	tableMask = tableSize - 1
	// 哈希表条目是uint32。零是无效项，因为
	// 有效条目的低12位必须是非文字代码。
	invalidEntry = 0
)

// 作者是LZW压缩机。它写入数据的压缩形式
// 到基础编写器（请参见NewWriter）。
type Writer struct {
	// w是写入压缩字节的写入器。
	w writer
	// 顺序、写入、位、nBits和宽度是的状态
	// 将代码流转换为字节流。
	order Order
	write func(*Writer, uint32) error
	bits  uint32
	nBits uint
	width uint
	// litWidth是以位为单位的文字代码宽度。
	litWidth uint
	// hi是下一个代码所隐含的代码。
	// 溢出是hi溢出代码宽度的代码。
	hi, overflow uint32
	// savedCode是最近一次写入结束时累积的代码
	// 呼叫如果没有这样的调用，则等于invalidCode。
	savedCode uint32
	// err是写入过程中遇到的第一个错误。关闭编写器
	// 将使任何未来的写调用返回errClosed
	err error
	// 表是从20位键到12位值的哈希表。每张桌子
	// 条目包含键<<12 | val和通过线性探测解决的冲突。
	// 键由12位代码前缀和8位字节后缀组成。
	// 这些值是一个12位代码。
	table [tableSize]uint32
}

// WriteSB为“最低有效位优先”数据写入代码c。
func (w *Writer) writeLSB(c uint32) error {
	w.bits |= c << w.nBits
	w.nBits += w.width
	for w.nBits >= 8 {
		if err := w.w.WriteByte(uint8(w.bits)); err != nil {
			return err
		}
		w.bits >>= 8
		w.nBits -= 8
	}
	return nil
}

// writeMSB为“最高有效位优先”数据编写代码c。
func (w *Writer) writeMSB(c uint32) error {
	w.bits |= c << (32 - w.width - w.nBits)
	w.nBits += w.width
	for w.nBits >= 8 {
		if err := w.w.WriteByte(uint8(w.bits >> 24)); err != nil {
			return err
		}
		w.bits <<= 8
		w.nBits -= 8
	}
	return nil
}

// errOutOfCodes是一个内部错误，表示写入程序已用完
// 下一步需要发送一个明确的代码。
var errOutOfCodes = errors.New("lzw: out of codes")

// incHi增加e.hi，并检查溢出和溢出
// 未使用的代码。在后一种情况下，incHi发送一个清除代码，重置
// 写入程序状态并返回错误代码。
func (w *Writer) incHi() error {
	w.hi++
	if w.hi == w.overflow {
		w.width++
		w.overflow <<= 1
	}
	if w.hi == maxCode {
		clear := uint32(1) << w.litWidth
		if err := w.write(w, clear); err != nil {
			return err
		}
		w.width = w.litWidth + 1
		w.hi = clear + 1
		w.overflow = clear << 1
		for i := range w.table {
			w.table[i] = invalidEntry
		}
		return errOutOfCodes
	}
	return nil
}

// Write将p的压缩表示形式写入w的底层writer。
func (w *Writer) Write(p []byte) (n int, err error) {
	if w.err != nil {
		return 0, w.err
	}
	if len(p) == 0 {
		return 0, nil
	}
	if maxLit := uint8(1<<w.litWidth - 1); maxLit != 0xff {
		for _, x := range p {
			if x > maxLit {
				w.err = errors.New("lzw: input byte too large for the litWidth")
				return 0, w.err
			}
		}
	}
	n = len(p)
	code := w.savedCode
	if code == invalidCode {
		// 发送的第一个代码始终是文本代码。
		code, p = uint32(p[0]), p[1:]
	}
loop:
	for _, x := range p {
		literal := uint32(x)
		key := code<<8 | literal
		// 如果这个键有一个哈希表命中，那么我们继续循环
		// 并且还没有发出代码。
		hash := (key>>12 ^ key) & tableMask
		for h, t := hash, w.table[hash]; t != invalidEntry; {
			if key == t>>12 {
				code = t & maxCode
				continue loop
			}
			h = (h + 1) & tableMask
			t = w.table[h]
		}
		// 否则，编写当前代码，文本将成为
		// 下一个发出的代码。
		if w.err = w.write(w, code); w.err != nil {
			return 0, w.err
		}
		code = literal
		// 增量e.hi，下一个隐含代码。如果代码用完，请重置
		// 写入程序状态（包括清除哈希表）并继续。
		if err1 := w.incHi(); err1 != nil {
			if err1 == errOutOfCodes {
				continue
			}
			w.err = err1
			return 0, w.err
		}
		// 否则，将key->e.hi插入e.table表示的映射中。
		for {
			if w.table[hash] == invalidEntry {
				w.table[hash] = (key << 12) | w.hi
				break
			}
			hash = (hash + 1) & tableMask
		}
	}
	w.savedCode = code
	return n, nil
}

// Close关闭写入程序，刷新所有挂起的输出。它不关
// w的潜在作者。
func (w *Writer) Close() error {
	if w.err != nil {
		if w.err == errClosed {
			return nil
		}
		return w.err
	}
	// 以后再调用Write return errClosed。
	w.err = errClosed
	// 如果有效，请写入保存的代码。
	if w.savedCode != invalidCode {
		if err := w.write(w, w.savedCode); err != nil {
			return err
		}
		if err := w.incHi(); err != nil && err != errOutOfCodes {
			return err
		}
	}
	// 编写eof代码。
	eof := uint32(1)<<w.litWidth + 1
	if err := w.write(w, eof); err != nil {
		return err
	}
	// 写最后一位。
	if w.nBits > 0 {
		if w.order == MSB {
			w.bits >>= 24
		}
		if err := w.w.WriteByte(uint8(w.bits)); err != nil {
			return err
		}
	}
	return w.w.Flush()
}

// 重置清除写入程序的状态，并允许重新使用它
// 作为一名新作家。
func (w *Writer) Reset(dst io.Writer, order Order, litWidth int) {
	*w = Writer{}
	w.init(dst, order, litWidth)
}

// NewWriter创建一个新io.WriteCloser。
// 对返回io.WriteCloser的写入被压缩并写入w。
// 调用方有责任在以下情况下调用WriteCloser上的Close
// 写完了。
// 用于文字代码的位数litWidth必须在
// 范围[2,8]，通常为8。输入字节的宽度必须小于1。
// None
// 可以保证返回的io.WriteCloser的基础类型
// 他是个作家。
func NewWriter(w io.Writer, order Order, litWidth int) io.WriteCloser {
	return newWriter(w, order, litWidth)
}

func newWriter(dst io.Writer, order Order, litWidth int) *Writer {
	w := new(Writer)
	w.init(dst, order, litWidth)
	return w
}

func (w *Writer) init(dst io.Writer, order Order, litWidth int) {
	switch order {
	case LSB:
		w.write = (*Writer).writeLSB
	case MSB:
		w.write = (*Writer).writeMSB
	default:
		w.err = errors.New("lzw: unknown order")
		return
	}
	if litWidth < 2 || 8 < litWidth {
		w.err = fmt.Errorf("lzw: litWidth %d out of range", litWidth)
		return
	}
	bw, ok := dst.(writer)
	if !ok && dst != nil {
		bw = bufio.NewWriter(dst)
	}
	w.w = bw
	lw := uint(litWidth)
	w.order = order
	w.width = 1 + lw
	w.litWidth = lw
	w.hi = 1<<lw + 1
	w.overflow = 1 << (lw + 1)
	w.savedCode = invalidCode
}
